Giấy cói Rhind (từ khoảng năm 1550 trước Công nguyên) có chứa các khai triển phân số Ai Cập theo nhiều dạng khác nhau cho số nguyên tố và hợp số.[13] Tuy nhiên, các công trình nghiên cứu cụ thể về số nguyên tố được lưu lại sớm nhất đến từ toán học Hy Lạp cổ đại. Bộ Cơ sở của Euclid (khoảng 300 TCN) có phần chứng minh sự tồn tại vô số số nguyên tố và định lý cơ bản của số học, đồng thời nêu cách tạo ra một số hoàn thiện từ số nguyên tố Mersenne.[14][15] Một phát minh khác từ Hy Lạp là sàng Eratosthenes vẫn còn được dùng để lập danh sách các số nguyên tố.[16][17]

Khoảng năm 1000, nhà toán học Hồi giáo Ibn al-Haytham (Alhazen) tìm ra định lý Wilson, xác định số nguyên tố là các số n {\displaystyle n} chia hết ( n − 1 ) ! + 1 {\displaystyle (n-1)!+1} . Ông cũng phỏng đoán rằng tất cả số hoàn thiện chẵn đều có thể được tạo ra từ số Mersenne theo cách xây dựng của Euclid, nhưng không chứng minh được.[18] Một nhà toán học Hồi giáo khác, Ibn al-Banna' al-Marrakushi tìm ra rằng sàng Eratosthenes có thể được đẩy nhanh khi chỉ kiểm tra các ước số lớn đến căn bậc hai của số lớn nhất được kiểm tra. Fibonacci sau đó đã mang những ý tưởng mới này từ toán học Hồi giáo về châu Âu. Cuốn Liber Abaci (1202) của ông là cuốn sách đầu tiên mô tả giải thuật chia thử để kiểm tra tính nguyên tố chỉ bằng việc kiểm tra các ước số lớn đến căn bậc hai của số cần kiểm tra.[17]

Năm 1640, Pierre de Fermat phát biểu định lý nhỏ Fermat (về sau được Leibniz và Euler chứng minh).[19] Fermat cũng đã nghiên cứu và kiểm tra tính nguyên tố của số Fermat 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} ,[20] và Marin Mersenne nghiên cứu số nguyên tố Mersenne, số nguyên tố có dạng 2 p − 1 {\displaystyle 2^{p}-1} với p {\displaystyle p} cũng là số nguyên tố.[21] Trong thư gửi Euler năm 1742, Christian Goldbach đã phát biểu giả thuyết Goldbach cho rằng mọi số chẵn đều là tổng của hai số nguyên tố.[22] Euler chứng minh được giả thuyết của Alhazen (về sau gọi là định lý Euclid–Euler) rằng mọi số hoàn thiện chẵn có thể được tạo ra từ số nguyên tố Mersenne.[15] Ông cũng giới thiệu các phương pháp được ứng dụng từ giải tích toán học trong lĩnh vực này khi chứng minh sự tồn tại vô số số nguyên tố và tính phân kỳ của tổng nghịch đảo các số nguyên tố 1 2 + 1 3 + 1 5 + 1 7 + 1 11 + ⋯ {\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots } .[23] Đầu thế kỷ 19, Legendre và Gauss đưa ra phỏng đoán rằng khi x {\displaystyle x} tiến về vô hạn thí số lượng số nguyên tố nhỏ hơn hoặc bằng x {\displaystyle x} tiệm cận về x / log ⁡ x {\displaystyle x/\log x} với log ⁡ x {\displaystyle \log x} là logarit tự nhiên của x {\displaystyle x} . Ý tưởng của Bernhard Riemann trong công trình năm 1859 về hàm zeta của ông đã góp phần vạch ra hướng đi để chứng minh phỏng đoán đó. Mặc dù một phỏng đoán liên quan là giả thuyết Riemann vẫn chưa có lời giải, đại cuơng của Riemann đã được hoàn thành vào năm 1896 bởi Hadamard và de la Vallée Poussin và kết quả này hiện được biết đến với tên gọi định lý số nguyên tố.[24] Một thành tựu quan trọng khác trong thế kỷ 19 là định lý Dirichlet về cấp số cộng cho rằng một cấp số cộng nhất định chứa vô số số nguyên tố.[25]

Nhiều nhà toán học đã nghiên cứu các thuật toán kiểm tra tính nguyên tố với các số lớn hơn so với các số mà giải thuật chia thử có thể áp dụng được. Các thuật toán giới hạn về một dạng số cụ thể bao gồm kiểm tra Pépin cho số Fermat (1877),[26] định lý Proth (khoảng 1878),[27] kiểm tra Lucas–Lehmer (1856) và dạng tổng quát của nó, kiểm tra Lucas.[17]

Từ năm 1951, tất cả các số nguyên tố lớn nhất đã biết đều được tìm ra thông qua các thuật toán trên máy tính.[lower-alpha 1] Công cuộc tìm ra số nguyên tố lớn hơn thế đã gây chú ý ngoài phạm vi toán học với dự án Great Internet Mersenne Prime Search và nhiều dự án điện toán phân tán khác.[8][29] Quan niệm rằng số nguyên tố ít được ứng dụng ngoài toán học thuần túy[lower-alpha 2] đã bị xóa bỏ vào những năm 1970 khi mật mã hóa khóa công khai và mã hóa RSA được phát minh dựa trên số nguyên tố.[32]

Tầm quan trọng ngày càng lớn của việc kiểm tra tính nguyên tố và phân tích số nguyên tố trên máy tính dẫn đến sự phát triển của nhiều thuật toán khác có thể thực hiện được với các số rất lớn không thuộc bất kỳ dạng đặc biệt nào.[16][33][34] Lý thuyết toán học về số nguyên tố cũng tiếp tục phát triển trong thời kỳ hiện đại với định lý Green–Tao (2004) phát biểu rằng tồn tại các cấp số cộng dài bất kỳ chỉ chứa số nguyên tố, và chứng minh của Yitang Zhang năm 2013 rằng tồn tại vô số khoảng cách nguyên tố với kích thước giới hạn.[35]

Tính nguyên tố của số 1

Đa số nhà toán học Hy Lạp cổ không cho rằng 1 là một số nên họ không thể xét được tính nguyên tố của nó.[36][37] Một số nhà toán học thời điểm đó cũng cho rằng số nguyên tố có được từ sự chia nhỏ các số lẻ nên họ không xem số 2 là số nguyên tố. Tuy nhiên, Euclid và đa số nhà toán học Hy Lạp cổ xem 2 là số nguyên tố. Các nhà toán học Hồi giáo cũng nối tiếp theo Hy Lạp, không công nhận 1 là một số.[36] Đến thời Trung Cổ và Phục Hưng, các nhà toán học bắt đầu thừa nhận 1 là một số, và một vài trong số đó cho rằng số 1 là số nguyên tố đầu tiên.[38] Giữa thế kỷ 18, Christian Goldbach công nhận số 1 là số nguyên tố trong thư gửi Leonhard Euler, nhưng Euler lại không thừa nhận như thế.[39] Nhiều nhà toán học thế kỷ 19 vẫn cho rằng 1 là số nguyên tố,[40] và danh sách số nguyên tố có chứa số 1 vẫn tiếp tục được xuất bản cho đến năm 1956.[41][42]

Nếu định nghĩa số nguyên tố bị thay đổi để công nhận 1 là số nguyên tố, nhiều định lý liên quan đến nó sẽ phải được diễn đạt lại một cách rắc rối. Chẳng hạn, định lý cơ bản của số học khi đó sẽ bị sửa lại về mặt phân tích thành các số nguyên tố lớn hơn 1, vì mọi số đều có vô số cách phân tích mà trong đó số 1 xuất hiện với số lần bất kỳ.[40] Tuơng tự, sàng Eratosthenes cũng sẽ không hoạt động đúng cách, vì khi đó nó loại bỏ tất cả các bội của 1 (tức là tất cả các số khác) và cho đầu ra chỉ có duy nhất số 1.[42] Một số tính chất của số nguyên tố cũng không đúng đối với số 1: ví dụ, công thức của hàm phi Euler hoặc hàm tổng các ước số khác nhau với số nguyên tố so với số 1.[43] Đến đầu thế kỷ 20, các nhà toán học bắt đầu thừa nhận rằng số 1 không nên nằm trong danh sách số nguyên tố, mà thay vào đó cần nằm trong khái niệm đặc biệt: "đơn vị" trong lý thuyết vành.[40]